{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python 3.6 - Dictionary Ordering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python 3.6 sees a new implementation of the standard `dict` that preserves key ordering (based on the order in which new keys are added into or removed from the dictionary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Although this is an implementation detail in 3.6, it is supposed to become official in Python 3.7. \n",
    "\n",
    "`https://mail.python.org/pipermail/python-dev/2017-December/151283.html`\n",
    "\n",
    "So it should be safe to now assume dictionary keys will retain order , and using an `OrderedDict` might no longer be needed for certain cases. I'll come back to `OrderedDict` in a bit...\n",
    "\n",
    "**Use for Python 3.6 and higher only!**\n",
    "\n",
    "If you use that ordering feature with standard `dict` objects and then try to run your code in a prior version, things will break :-)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also means that `keys()` (that iterate from left to right) preserves order as does `values()`. On the other hand `popitem()` will pop right-most element from dictionary. Sounds like stack behavior to me - but does not mean you should use it as such - I'm pretty sure that's not going to be as efficient as say using a list!."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see some of this (just make sure you're running 3.6 or higher)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sys import version_info"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sys.version_info(major=3, minor=6, micro=2, releaselevel='final', serial=0)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "version_info"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d = {'a': 1, 'b': 2}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(dict_keys(['a', 'b']), dict_values([1, 2]), dict_items([('a', 1), ('b', 2)]))"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.keys(), d.values(), d.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d['x'] = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(dict_keys(['a', 'b', 'x']),\n",
       " dict_values([1, 2, 3]),\n",
       " dict_items([('a', 1), ('b', 2), ('x', 3)]))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.keys(), d.values(), d.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "del d['b']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(dict_keys(['a', 'x']), dict_values([1, 3]), dict_items([('a', 1), ('x', 3)]))"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.keys(), d.values(), d.items()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d['b'] = 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(dict_keys(['a', 'x', 'b']),\n",
       " dict_values([1, 3, 4]),\n",
       " dict_items([('a', 1), ('x', 3), ('b', 4)]))"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.keys(), d.values(), d.items()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What about replacing a value for an existing key?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d['x'] =100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(dict_keys(['a', 'x', 'b']),\n",
       " dict_values([1, 100, 4]),\n",
       " dict_items([('a', 1), ('x', 100), ('b', 4)]))"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.keys(), d.values(), d.items()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Order maintained..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And if we pop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('b', 4)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.popitem()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We popped the last item."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So now I'm left wondering how to pick a *random* item from the dictionary?\n",
    "(Not that we could before - it might have looked random when we popped an item but it wasn't)\n",
    "\n",
    "Sounds like another video :-)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Important note:** Be careful of Jupyter notebooks - something I just realized - take a look:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d = {'x': 1, 'a': 2}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'x': 1, 'a': 2}\n"
     ]
    }
   ],
   "source": [
    "print(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 2, 'x': 1}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how just letting Jupyter display `d` changed the display order of the keys? (I'm guessing its doing something similar to `prettyprint` (or maybe even using it), which changes the displayed key order to be lexicographical."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What about using `update` to update one dict based on another (inserting missing keys, and updating common ones - but especially the insertion bit) - I'm guessing the order is retained with any insertions appearing at the end and ordered according to the dict being merged in. Let's see:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d1 = {'a': 1, 'b': 200}\n",
    "d2 = {'a': 100, 'd':300, 'c':400}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d1.update(d2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 100, 'b': 200, 'd': 300, 'c': 400}\n"
     ]
    }
   ],
   "source": [
    "print(d1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Back to `OrderedDict` for a second:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`OrderedDict` has a few methods that afaik have no equivalent (yet) in standard dicts:\n",
    "* `move_to_end(key, last=True)` - either move to front or back\n",
    "* `popitem(last=True)` - that can pop either from front or back of dict\n",
    "* supports reverse iteration using `reversed()`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take each one of those one by one:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**move to end:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start: {'a': 1, 'b': 2, 'c': 3}\n",
      "moved a to end: {'b': 2, 'c': 3, 'a': 1}\n"
     ]
    }
   ],
   "source": [
    "d = {'a':1, 'b':2, 'c':3}\n",
    "print('start:', d)\n",
    "d['a'] = d.pop('a')\n",
    "print('moved a to end:',d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**move to front:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's one not so easy, the only option I can think of is to move all the keys around to re-order. Maybe something like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start: {'a': 1, 'b': 2, 'c': 3, 'x': 100, 'y': 200}\n",
      "moved c to end: {'a': 1, 'b': 2, 'x': 100, 'y': 200, 'c': 3}\n",
      "moved c to front: {'c': 3, 'a': 1, 'b': 2, 'x': 100, 'y': 200}\n"
     ]
    }
   ],
   "source": [
    "d = {'a':1, 'b':2, 'c':3, 'x':100, 'y':200}\n",
    "print('start:', d)\n",
    "d['c'] = d.pop('c')\n",
    "print('moved c to end:', d)\n",
    "\n",
    "for i in range(len(d)-1):\n",
    "    key = next(iter(d.keys()))\n",
    "    d[key] = d.pop(key)\n",
    "print('moved c to front:', d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**pop last item:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That one's trivial - just use `popitem`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start: {'a': 1, 'b': 2, 'c': 3, 'x': 100, 'y': 200}\n",
      "pop last item: {'a': 1, 'b': 2, 'c': 3, 'x': 100}\n"
     ]
    }
   ],
   "source": [
    "d = {'a':1, 'b':2, 'c':3, 'x':100, 'y':200}\n",
    "print('start:', d)\n",
    "d.popitem()\n",
    "print('pop last item:', d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**pop first item:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not too difficult - we just need to identify the *first* key, and pop it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start: {'a': 1, 'b': 2, 'c': 3, 'x': 100, 'y': 200}\n",
      "pop first item: {'b': 2, 'c': 3, 'x': 100, 'y': 200}\n"
     ]
    }
   ],
   "source": [
    "d = {'a':1, 'b':2, 'c':3, 'x':100, 'y':200}\n",
    "print('start:', d)\n",
    "key = next(iter(d.keys()))\n",
    "d.pop(key)\n",
    "print('pop first item:', d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you're interested, here's Raymond Hettinger's pure Python \"version\" of his C dict implementation:\n",
    "`http://code.activestate.com/recipes/578375/`"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
